import java.util.Stack;

public class InOrderTraversalBinaryTree {

    static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int v){
            this.val = v;
            this.left = null;
            this.right = null;
        }
    }

    static void InOrderTra(TreeNode root){
        if(root == null) return;

        if(root.left != null) InOrderTra(root.left);
        System.out.println(root.val);
        if(root.right != null) InOrderTra(root.right);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(7);
        TreeNode left = new TreeNode(3);
        TreeNode right = new TreeNode(10);
        root.left = left;
        root.right = right;
//      递归法
//        InOrderTra(root);

        Stack<TreeNode> st = new Stack<>();
        if(root != null)
            st.push(root);
        while(!st.isEmpty()){
            TreeNode node = st.peek();
            if(node != null){
                st.pop();

                if(node.right != null) st.push(node.right);
                st.push(node);
                st.push(null);
                if(node.left != null) st.push(node.left);
            }else{
                st.pop();
                node = st.peek();
                st.pop();
                System.out.println(node.val);
            }

        }

    }

}
